package www.study.com;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

//组合总和 https://leetcode.cn/problems/combination-sum/   需要再看下标准代码 【非最优解：方式二】
public class code39 {
    public static void main(String[] args) {

    }

    class Solution {
        List<List<Integer>> ans = new ArrayList<>();
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            List<Integer> tmp = new ArrayList<>();
            Arrays.sort(candidates);
            DFS(tmp,0,target,0,candidates);
            return ans;
            // List<List<Integer>> res = new ArrayList<>();
            // dfs(candidates,0,target,0,new ArrayList<>(),res);
            // return res;
        }
        //方式二：见二哥
        public void DFS(List<Integer> tmp,int now,int target,int begin,int[] candidates){
            if(now == target){
                ans.add(new ArrayList<>(tmp));
                return;
            }
            for(int i = begin ; i < candidates.length ; i++){
                if(now + candidates[i] > target) return;
                tmp.add(candidates[i]);
                DFS(tmp,now + candidates[i],target,i,candidates);
                tmp.remove(tmp.size() - 1);
            }
        }
        //方式一
        public void dfs(int[] candidates,int i,int target,int now,List<Integer> kept,List<List<Integer>> res){
            if(i == candidates.length || now == target){
                if(now == target){
                    List<Integer> newList = kept.stream().collect(Collectors.toList());//new ArrayList<>();
                    //Collections.copy(newList,kept);
                    res.add(newList);//(kept.stream().collect(toList()));
                }
                return;
            }
            if(now > target) return;
            //dfs(candidates,i+1)
            int cnt = 1;
            for( ; cnt * candidates[i] + now <= target ; cnt++){
                kept.add(candidates[i]);
                dfs(candidates,i+1,target,now+cnt*candidates[i],kept,res);
            }
            //回溯
            cnt--;
            if(cnt > 0){
                kept.subList(kept.size() - cnt, kept.size()).clear();
                //kept.removeRange(kept.size() - cnt,kept.size()); ArrayList没有这个API
            }
            dfs(candidates,i+1,target,now,kept,res);
        }
    }
}
